#include <iostream>
#include <windows.h>
using namespace std;

const long long int num = 3500000;
long long int* arr;
int COUNT = 1000;//��β���ȡƽ��ֵ
long long int sum = 0;

void init() {
    arr = new long long int[num];
    for (int i = 0; i < num; i++) {
        arr[i] = i;
    }
    sum = 0;
}
void del() {
    delete[]arr;
    sum = 0;
}
//ƽ���㷨
void summing_normal() {
    long long int head1, tail1, freq1;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq1);
    QueryPerformanceCounter((LARGE_INTEGER*)&head1);
    for (int c = 0; c < COUNT; c++) {
        sum = 0;
        for (int i = 0; i < num; i++)
            sum += arr[i];
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&tail1);
    cout << "summing_normal_chain:" << (tail1 - head1) * 1000.0 / freq1 / COUNT << "ms" << endl;
}
//��·��ʽ
void summing_multi_way_chain(){
    long long int head2, tail2, freq2;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq2);
    QueryPerformanceCounter((LARGE_INTEGER*)&head2);
    for (int c = 0; c < COUNT; c++) {
        long long int sum1 = 0, sum2 = 0;
        for (int i = 0; i < num - 1; i += 2) {
            sum1 += arr[i];
            sum2 += arr[i + 1];
        }
        sum = sum1 + sum2;
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&tail2);
    cout << "summing_multi_way_chain:" << (tail2 - head2) * 1000.0 / freq2 / COUNT << "ms" << endl;
    
}
//�ݹ麯��
void summing_recursive(long long int n) {
    if (n == 1) {
        return;
    }
    else {
        for (long long int i = 0; i < n / 2; i++) {
            arr[i] += arr[n - i - 1];
        }
        n = n / 2;
        summing_recursive(n);
    }
}
void summing_recurse() {
    long long int head3, tail3, freq3;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq3);
    QueryPerformanceCounter((LARGE_INTEGER*)&head3);
    for (int c = 0; c < COUNT; c++) {
        long long int n = num;
        summing_recursive(n);
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&tail3);
    cout << "summing_recurse:" << (tail3 - head3) * 1000.0 / freq3 / COUNT << "ms" << endl;
}
//����ѭ��
void summing_cycles() {
    long long int head4, tail4, freq4;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq4);
    QueryPerformanceCounter((LARGE_INTEGER*)&head4);
    for (int c = 0; c < COUNT; c++) {
        long long int m = num;
        for (; m > 1; m /= 2) {
            for (int i = 0; i < m / 2; i++) {
                arr[i] = arr[i * 2] + arr[i * 1 + 1];
            }
        }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&tail4);
    cout << "summing_double_cycles:" << (tail4 - head4) * 1000.0 / freq4 / COUNT << "ms" << endl;
}

int main()
{
    init();
    summing_normal();
    del();

    init();
    summing_multi_way_chain();
    del();

    init();
    summing_recurse();
    del();

    init();
    summing_cycles();
    del();

    return 0;
}